package com.jia.leetCode;

import java.util.HashMap;
import java.util.Map;

public class Pro0169 {
	//5.分治
	public int majorityElement(int[] array) {
		int result = divide(array, 0, array.length - 1);
		return checkMoreThanHalf(array, result)? result : -1;
	}
	private int divide(int[] array, int st, int ed) {
		if(st == ed) {
			return array[st]; }
		else {
			int mid = st + ((ed - st) >> 1);
			int leftMajority = divide(array, st, mid);
			int rightMajority = divide(array, mid + 1, ed);
			int countleftMajority = countMajority(array, st, mid, leftMajority);
			int countRightMajority = countMajority(array, mid + 1, ed ,rightMajority);
			return countleftMajority > countRightMajority? leftMajority : rightMajority;
		}
	}
	private int countMajority(int[] array, int st, int ed, int num) {
		int count = 0;
		for(int i = st; i <=ed ; i++) {
			if(num == array[i]) {
				++count;
			}
		}
		return count;
	}


	//4.位运算    Integer  32bit，每个位1个数大于一半，加入结果中
	public int majorityElement5(int[] array) {
		int ans = 0;
		int index = 1;
		int countOne = 0;
		for(int i = 0; i < 32; i++) {
			index = 1<<i;
			countOne = 0;
			for(int num : array) {
				if((num & index)!=0) {
					countOne++;
				}
			}
			if(countOne > array.length / 2) {
				ans |= index;
			}
		}
		return checkMoreThanHalf(array, ans)? ans : -1;
	}

	//3.计数
	public int majorityElement3(int[] array) {
		HashMap<Integer,Integer> map = new HashMap<>();//<num,count>
		for(int num : array) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}
		int len = array.length / 2;
		for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
			if(entry.getValue() > len) {
				return entry.getKey();
			}
		}
		return -1;
	}
	//2.摩尔投票
	public int majorityElement2(int[] array) {
		int major = 0, count = 0;
		for(int n : array) {
			if(count == 0) {
				++count;
				major = n;
			}else {
				if(major == n) {
					++count;
				}else {
					--count;
				}
			}
		}
		return checkMoreThanHalf(array,major)? major : -1;
	}

	/**
	 * 1.使用快排中的partition找出中位数，再利用中位数进行统计是否符合要求超过一半的数
	 */

	public int majorityElement1(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		int result = partition(array, 0, array.length - 1);
		if (checkMoreThanHalf(array, result)) {
			return result;
		}
		return 0;
	}

	private boolean checkMoreThanHalf(int[] array, int result) {
		int len = array.length;
		int count = 0;
		for (int val : array) {
			if (result == val) {
				++count;
			}
			if (count > len / 2)
				return true;
		}
		return false;
	}

	private int partition(int[] array, int start, int end) {
		/*** 快排partition函数原代码——start ***/
		int left = start;
		int right = end;

		int p = array[start];
		while (left < right) {
			while (left < right && array[right] >= p) right--;
			;
			if (left < right)
				array[left++] = array[right];
			while (left < right && array[left] <= p) left++;
			;
			if (left < right)
				array[right--] = array[left];
		}
		array[left] = p;

		/*** 定位判断 ***/
		if (left == array.length / 2) {
			return array[left];
		} else if (left > array.length / 2) {
			return partition(array, start, left - 1);
		} else {
			return partition(array, left + 1, end);
		}
	}
	public static void main(String[] args) {
		int[] array = {3,2,3};
		Pro0169 pro0169 = new Pro0169();
		System.out.println(pro0169.majorityElement(array));
	}
}
